var root = {
  val: '1',
  left: {
    val: '2',
    left: {
      val: '3',
      left: null,
      right: null
    },
    right: {
      val: '4',
      left: null,
      right: null
    }
  },
  right: {
    val: '5',
    left: {
      val: '6',
      left: null,
      right: null
    },
    right: {
      val: '7',
      left: null,
      right: null
    }
  },
}

// 递归版的先序遍历
function pre(node) {
  if(!node) return
  console.log(node.val)
  pre(node.left)
  pre(node.right)
}
// pre(root)
// 中序遍历
function mid(node) {
  if(!node) return
  mid(node.left)
  console.log(node.val)
  mid(node.right)
}
// mid(root)
// 后序遍历
function post(node) {
  if(!node) return
  post(node.left)
  post(node.right)
  console.log(node.val)
}
// post(root)
// 非递归版本的
// 先序遍历
function preNoRecursion(root) {
  let stack = [root]
  while(stack.length) {
    let item = stack.pop()
    console.log(item.val)
    item.right&&stack.push(item.right)
    item.left&&stack.push(item.left)
  }
}
// preNoRecursion(root)
// 中序遍历
function midNoRecursion(root) {
  let stack = []
  let p = root
  while(stack.length || p) {
    while(p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    console.log(n.val)
    p = n.right
  }
}
// midNoRecursion(root)
// 后序遍历
function postNoRecursion(root) {
  let stack = [root]
  let allStack = []
  while(stack.length) {
    let item = stack.pop()
    allStack.push(item)
    item.left&&stack.push(item.left)
    item.right&&stack.push(item.right)
  }
  while(allStack.length) {
    let n = allStack.pop()
    console.log(n.val)
  }
  // console.log(allStack)
}
postNoRecursion(root)